<head>
    <meta charset="UTF-8">
<title>算法训练 Pocket</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>日式的折纸手工&mdash;&mdash;一种折纸的艺术&mdash;&mdash;常常需要用到&ldquo;口袋&rdquo;的概念，特别是在那些复杂的、各个折纸模型需要通过口袋来实现嵌套的作品中。在这题中，我们需要数一数，一个正方形纸片折叠后形成了多少个口袋。一个口袋定义为：在折好的纸片中，从边界上可以看到的一个开口（两层纸之间的开口）。注意：一个开口可能被记作多个口袋，因为它可能可以从多个方向看到。图1展示了这样一个例子。注意到，&ldquo;中间&rdquo;的那个开口（第二和第三层之间的开口）被算了三次。</div>
<div>&nbsp;</div>
<div>图1：</div>
<div>&nbsp;</div>
<div><img src="http://lx.lanqiao.cn/RequireFile.do?fid=2egMbRRA" width="585" height="177" alt="" /></div>
<div>我们假设这个纸片一开始平放在桌面上，并且任意时刻都不会被完全从桌面上拿起。每次折叠要么是水平的、要么是垂直的，并且折叠只能沿着预先标好的N条水平线和N条垂直线。没有折叠的时候，水平线从上到下1~N标号，垂直线从左到右1~N标号。每次折叠，我们沿着一条线，和一个方向，把当前的矩形折成一个更小的矩形。例如，'2 U'表示沿着第二条水平线向上折；'1 L'表示沿着第一条垂直线向左折。折叠后，一条线可能有多个表示方法。（例如，图2中，第一次折叠后，'1 D'和'3 D'是等价的指令了）。最后，整个纸片被折成1*1的正方形，这时我们来统计它的口袋数量。保证每次操作都是合法的，并且这里我们忽略纸片的厚度。</div>
<div>&nbsp;</div>
<div>图2：</div>
<div>&nbsp;</div>
<div><img src="http://lx.lanqiao.cn/RequireFile.do?fid=febGLLJh" width="633" height="220" alt="" /></div>
<p>【输入格式】</p>
<p>输入第一行两个正整数N、K，N表示横向（也是纵向）的折痕数，K表示折叠操作数。水平线从上到下1~N标号，垂直线从左到右1~N标号。</p>
<p>接下来K行，每行由一个正整数和一个字符组成。正整数表示沿着哪条线折叠，字符表示折叠方向。（U为向上、D为向下；L为向左，R为向右）。折痕是水平的还是垂直的由折叠方向决定。</p>
<p>保证最终折成了1*1的正方形。</p>
<p><br />
【输出格式】</p>
<p>&nbsp;</p>
<p><br />
输出一行一个正整数，口袋数。</p>
<p>&nbsp;</p>
<p><br />
【样例输入】</p>
<p>3 5</p>
<p>2 U</p>
<p>1 L</p>
<p>3 D</p>
<p>3 R</p>
<p>2 L</p>
<pre><br /></pre>
<p>【样例输出】</p>
<p>&nbsp;</p>
<p>17</p>
<p>&nbsp;</p>
<p><br />
【数据规模和约定】</p>
<p>对于25%的数据，N&lt;=3.</p>
<p>对于50%的数据，N&lt;=5.</p>
<p>对于100%的数据，N&lt;=64，K&lt;=64</p>